The Euler number of a binary image is an important topological property for pattern recognition, and can be calculated by counting certain bit-quads in the image. This paper proposes an efficient strategy for improving the bit-quad-based Euler number computing algorithm. By use of the information obtained when processing the previous bit quad, the number of times that pixels must be checked in processing a bit quad decreases from 4 to 2. Experiments demonstrate that an algorithm with our strategy significantly outperforms conventional Euler number computing algorithms.

This paper proposes a new scheme that can evaluate the cell throughput performance of wireless local area network (LAN) systems, which use carrier sense multiple access/collision avoidance (CSMA/CA) and multiple transmission bit-rates (multi-rate). We extend the interference model of the conventional scheme in order to deal with interference more accurately in multi-cell environments. Unlike the conventional scheme, the proposed scheme is able to handle multi-rate systems. We use the proposed scheme to evaluate the IEEE 802.11a system and systems whose signal-bandwidth is expanded from that of the IEEE 802.11a system. We find that a system with 35(75) MHz signal-bandwidth achieves about 1.3(1.25) times higher cell throughput than the IEEE 802.11a system. Furthermore, the system with 35(75) MHz signal-bandwidth is also shown to have the potential to achieve up to 1.5(1.8) times higher cell throughput performance than the IEEE 802.11a system if the transmission efficiency on the media access control (MAC) layer is assumed to be ideal. It is concluded that the proposed scheme confirms that the approach to expand the signal bandwidth of the IEEE 802.11a system is effective to improve the cell throughput performance. This result is virtually impossible to derive with the conventional scheme.

Silva et al. has suggested a criterion based on incidence matrix to verify if a given extended free choice net has a live and bounded marking. This paper shows that this criterion is a necessary and sufficient condition that a given net is a state machine allocatable (SMA) net. This result gives a polynomial algorithm to verify SMA net.

Petri net is a graphical and mathematical modeling tool for discrete event systems. This paper treats analysis problems for Petri nets under the earliest firing rule. Under this firing rule, transitions must fire as soon as they are enabled. Marked Petri nets under the earliest firing rule are called earliest firing systems, for short. First, some relations in analysis problems between the earliest and the normal firing systems are discussed. These problems include deadlock freedom, boundedness, persistency and liveness. Then, relations among three types of reachability are considered from the viewpoint of the earliest firing rule. Since earliest firing systems can simulate register machines, they have equivalent modeling powers to Turing machines. It suggests, however, that most of the analysis problems of earliest firing systems with general net structures are undecidable. In this paper, net structures are restricted to a subclass called dissynchronous choice (DC) nets. It is shown that the reachability problem from an initial marking to dead markings (markings where no transition can fire) in earliest firing DC systems is equivalent to the usual reachability problem of the same systems under the normal firing rule. Then, the result is applied to reachability problems of controlled DC systems in which some transitions in the net have external control input places. It is shown that for systems where every transition in the net has an external control input place, one type of reachability problem is decidable. Lastly, the liveness problem of earliest firing DC systems is considered and it is shown that this problem is equivalent to that of the underlying DC system under the normal firing rule. It is also shown that this liveness problem is decidable.

This paper proposes a reduced-complexity signal detection scheme for Orthogonal Frequency Division Multiplexing with Space Division Multiplexing (OFDM/SDM) systems that utilize Zero-Forcing (ZF) and K-best algorithms. It is known that Maximum Likelihood Detection (MLD) with exhaustive search achieves mathematically optimal performance for SDM signal detection. However, it also suffers from exponential computational complexity against the number of transmit antennas and modulation order. In order to reduce the computational complexity of MLD, we apply the K-best algorithm for signal detection. It is known that the K-best algorithm itself inherently reduces the computational complexity of MLD because it avoids exhaustive search. In this paper, we propose the modified K-best algorithm, which exploits the ZF algorithm for initial symbol estimation. This initial symbol estimation improves the decoding accuracy of the original K-best algorithm. We evaluate the performance of the proposed scheme through computer simulations. The computer simulation results show that the performance degradation from the MLD algorithm is suppressed to just 1 dB or so in terms of the required Eb/N0 for packet error rate (PER) = 10-2, When either 16 Quadrature Amplitude Modulation (16QAM) or 64QAM is applied with three transmit and three receive antennas. In these cases, 87% and 99% fewer metric computations are required than the MLD algorithm. It is confirmed that the proposed MLD algorithm offers a significant reduction in the computational complexity from the MLD algorithm while suppressing the performance degradation.

This letter treats computational complexity of bounded asymmetric choice (AC) net. AC net is a subclass of Petri net that properly includes the class of well-known extended free choice net. It is shown that satisfiability problem of Boolean expressions is polynomial time reducible to liveness problem of bounded AC nets. This implies that the problem is NP-hard.

Petri net is a powerful modeling tool for concurrent systems. Liveness, which is a problem to verify there exists no local deadlock, is one of the most important properties of Petri net to analyze. Computational complexity of liveness of a general Petri net is deterministic exponential space. Liveness is studied for subclasses of Petri nets to obtain necessary and sufficient conditions that need less computational cost. These are mainly done using a subset of places called siphons. CS-property, which denotes that every siphon has token(s) in every reachable marking, in one of key properties in liveness analysis. On the other hand, normal Petri net is a subclass of Petri net whose reachability set can be effectively calculated. This paper studies computational complexity of liveness problem of normal Petri nets. First, it is shown that liveness of a normal Petri net is equivalent to cs-property. Then we show this problem is co-NP complete by deriving a nondeterministic algorithm for non-liveness which is similar to the algorithm for liveness suggested by Howell et al. Lastly, we study structural feature of bounded Petri net where liveness and cs-property are equivalent. From this consideration, liveness problem of bounded normal Petri net is shown to be deterministic polynomial time complexity.

This paper proposes a new multi-task synchronization scheme for packet mode orthogonal frequency division multiplexing (OFDM) signals in multi-input multi-output (MIMO) transmission systems; it targets high-rate wireless LANs that offer over 100 Mbit/s. In addition, this paper introduces a packet format for MIMO-OFDM signals that ensures backward compatibility with IEEE 802.11a. The proposed synchronization scheme has simple open-loop construction and consists of automatic frequency control (AFC), symbol timing detection, MIMO channel estimation, and phase tracking. AFC and symbol timing detection are carried out in the time-domain. After OFDM demodulation, the proposed scheme performs MIMO channel estimation and phase tracking in the frequency-domain. Considering all of the above synchronization tasks, we evaluate the packet error rate (PER) performance using the IEEE 802.11 TGn-defined channel model-D and model-E. In channel model-D with the RMS delay spread = 50 ns, the proposed scheme shows superior performance; it suppress the required Eb/N0 degradation to within 0.4 dB with 1000 byte packets compared to the performance achieved if only MIMO channel estimation is considered. Moreover, in channel model-E with the RMS delay spread = 100 ns, it is found that the proposed scheme degrades the required Eb/N0 only by approximately 1.5 dB compared to the MIMO channel estimation only case, even if the packet length is 1000 bytes with 64QAM and coding-rate = 7/8.

This paper presents experimental results of our proposed null-space expansion scheme for multiuser massive multiple-input multiple-output (MIMO) in time varying channels. Multiuser MIMO transmission with the proposed scheme can suppress the inter-user interference (IUI) caused by outdated channel state information (CSI). The excess degrees of freedom (DoFs) of massive MIMO is exploited to perform additional null-steering using past estimated CSI. The signal-to-interference power ratio (SIR) and spectral efficiency performances achieved by the proposed scheme that uses measured CSI is experimentally evaluated. It is confirmed that the proposed scheme shows performance superior to the conventional channel prediction scheme. In addition, IUI can be stably suppressed even in high mobility environments by further increasing the null-space dimension.

This paper proposes a practical application of Massive MIMO technology, Massive Antenna Systems for Wireless Entrance (MAS-WE), and along with related inter-user interference cancellation (IUIC) and scheduling techniques. MAS-WE, in which the entrance base station (EBS) employs a large number of antennas, can effectively provide high capacity wireless entrance links to a large number of access points (APs) distributed over a wide coverage area. The proposed techniques are simplified to practical implementation; EBS side uses around 100 antenna elements to spatially multiplex more than 16 signal streams. SIR performance is evaluated by system level simulations that consider imperfect channel state information (CSI). The results show that MAS-WE with the proposed techniques can reliably achieve high spectral efficiency with high level space division multiplexing.

This paper proposes an antenna selection method for terminal antennas employing orthogonal polarizations and patterns, which is suitable for outdoor MultiUser Multi-Input Multi-Output (MU-MIMO) systems. In addition, this paper introduces and verifies two other antenna selection methods for comparison. For the sake of simplicity, three orthogonal dipoles are considered, and this antenna configuration using the proposed selection method is compared to an antenna configuration with three vertical or horizontal dipoles. In the proposed antenna selection method, we always choose the vertical dipole, and choose one of two horizontal dipoles, which are orthogonal to each other, based on the Signal-to-Noise Ratio (SNR). We measured the MU-MIMO transmission properties and found that the proposed selection method employing the antenna with orthogonal polarizations and patterns can offer fairly high channel capacity in a multiuser scenario.

Most of scientists except computer scientists do not want to make efforts for performance tuning with rewriting their MPI applications. In addition, the number of processing elements which can be used by them is increasing year by year. On large-scale parallel systems, the number of accumulated messages on a message buffer tends to increase in some of their applications. Since searching message queue in MPI is time-consuming, system side scalable acceleration is needed for those systems. In this paper, a support function named LHS (Limited-length Head Separation) is proposed. Its performance in searching message buffer and hardware cost are evaluated. LHS accelerates searching message buffer by means of switching location to store limited-length heads of messages. It uses the effects such as increasing hit rate of cache on host with partial off-loading to hardware. Searching speed of message buffer when the order of message reception is different from the receiver's expectation is accelerated 14.3 times with LHS on FPGA-based network interface card (NIC) named DIMMnet-2. This absolute performance is 38.5 times higher than that of IBM BlueGene/P although the frequency is 8.5times slower than BlueGene/P. LHS has higher scalability than ALPU in the performance per frequency. Since these results are obtained with partially on loaded linear searching on old Pentium®4, performance gap will increase using state of art CPU. Therefore, LHS is more suitable for larger parallel systems. The discussions for adopting proposed method to state of art processors and systems are also presented.

Petri net is an efficient model for concurrent systems. Liveness is one of analysis properties of Petri net. It concerns with potential fireability of transitions. Many studies have been done on liveness of Petri nets and subclasses are suggested with liveness criteria. In this paper, extended partially ordered condition (EPOC) net is suggested and its liveness is studied. Equivalence of liveness and place-liveness is derived. Analysis using siphon and traps are done. Liveness under the earliest firing rule, where transition must fire as soon as it is enabled, is also studied.